<html>
  <head>
    <meta charset="utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1" />
<title>2、数据结构之队列 | 清汤牛肉锅</title>
<meta name="description" content="温故而知新
" />
<link rel="shortcut icon" href="https://ArtZoick.github.io//favicon.ico?v=1572228390311">
<link rel="stylesheet" href="https://use.fontawesome.com/releases/v5.7.2/css/all.css" integrity="sha384-fnmOCqbTlWIlj8LyTjo7mOUStjsKC4pOpQbqyi7RrhN7udi9RwhKkMHpvLbHG9Sr" crossorigin="anonymous">
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.10.0/katex.min.css">
<link rel="stylesheet" href="https://ArtZoick.github.io//styles/main.css">

<script src="https://cdn.bootcss.com/highlight.js/9.12.0/highlight.min.js"></script>
<link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Droid+Serif:400,700">


<script async src="https://www.googletagmanager.com/gtag/js?id=UA-143265163-1"></script>
<script>
  window.dataLayer = window.dataLayer || [];
  function gtag(){dataLayer.push(arguments);}
  gtag('js', new Date());

  gtag('config', 'UA-143265163-1');
</script>


  </head>
  <body>
    <div class="main">
      <div class="main-content">
        <div class="site-header">
  <a href="https://ArtZoick.github.io/">
  <img class="avatar" src="https://ArtZoick.github.io//images/avatar.png?v=1572228390311" alt="">
  </a>
  <h1 class="site-title">
    清汤牛肉锅
  </h1>
  <p class="site-description">
    温故而知新

  </p>
  <div class="menu-container">
    
      
        <a href="/" class="menu">
          首页
        </a>
      
    
      
        <a href="/archives" class="menu">
          归档
        </a>
      
    
      
        <a href="/tags" class="menu">
          标签
        </a>
      
    
      
        <a href="/post/about" class="menu">
          关于
        </a>
      
    
      
        <a href="/post/beef" class="menu">
          牛肉锅
        </a>
      
    
  </div>
  <div class="social-container">
    
      
    
      
    
      
    
      
    
      
    
  </div>
</div>

        <div class="post-detail">
          <article class="post">
            <h2 class="post-title">
              2、数据结构之队列
            </h2>
            <div class="post-info">
              <span>
                2019-09-27
              </span>
              <span>
                8 min read
              </span>
              
                <a href="https://ArtZoick.github.io//tag/数据结构与算法" class="post-tag">
                  # 数据结构与算法
                </a>
              
            </div>
            
            <div class="post-content-wrapper">
              <div class="post-content">
                <h2 id="1-实际应用场景">1、实际应用场景</h2>
<p>银行排队</p>
<h2 id="2-队列介绍">2、队列介绍</h2>
<ol>
<li>队列是一个 有序列表，可以用 数组或是 链表来实现。</li>
<li>遵循 先入先出的原则。即： 先存入队列的数据，要先取出。后存入的要后取出</li>
<li>示意图：(使用数组模拟队列示意图)</li>
</ol>
<img src="file://C:/Users/zoick/OneDrive/Gridea/post-images/datastructure/array/4.png" style="zoom: 80%;" />
<h2 id="3-数组模拟队列思路">3、数组模拟队列思路</h2>
<ul>
<li>队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图, 其中 maxSize 是该队列的最大容量。</li>
<li>因为队列的输出、输入是分别从前后端来处理，因此需要两个变量 front 及 rear 分别记录队列前后端的下标，front 会随着数据输出而改变，而 rear 则是随着数据输入而改变，如图所示:</li>
</ul>
<img src="file://C:/Users/zoick/OneDrive/Gridea/post-images/datastructure/array/4.png" style="zoom: 80%;" />
<ul>
<li>当我们将数据存入队列时称为”addQueue”，addQueue 的处理需要有两个步骤：思路分析
<ol>
<li>将尾指针往后移：rear+1 , 当 front == rear 【空】</li>
<li>若尾指针 rear 小于队列的最大下标 maxSize-1，则将数据存入 rear 所指的数组元素中，否则无法存入数据。<br>
rear == maxSize - 1【队列满】</li>
</ol>
</li>
</ul>
<h2 id="4-代码实现">4、代码实现</h2>
<pre><code class="language-java">package datastructure.array;

import java.util.Scanner;

public class ArrayQueueDemo {

	public static void main(String[] args) {
		//测试一把
		//创建一个队列
		ArrayQueue queue = new ArrayQueue(3);
		char key = ' '; //接收用户输入
		Scanner scanner = new Scanner(System.in);//
		boolean loop = true;
		//输出一个菜单
		while(loop) {
			System.out.println(&quot;s(show): 显示队列&quot;);
			System.out.println(&quot;e(exit): 退出程序&quot;);
			System.out.println(&quot;a(add): 添加数据到队列&quot;);
			System.out.println(&quot;g(get): 从队列取出数据&quot;);
			System.out.println(&quot;h(head): 查看队列头的数据&quot;);
			key = scanner.next().charAt(0);//接收一个字符
			switch (key) {
				case 's':
					queue.showQueue();
					break;
				case 'a':
					System.out.println(&quot;输出一个数&quot;);
					int value = scanner.nextInt();
					queue.addQueue(value);
					break;
				case 'g': //取出数据
					try {
						int res = queue.getQueue();
						System.out.printf(&quot;取出的数据是%d\n&quot;, res);
					} catch (Exception e) {
						// TODO: handle exception
						System.out.println(e.getMessage());
					}
					break;
				case 'h': //查看队列头的数据
					try {
						int res = queue.headQueue();
						System.out.printf(&quot;队列头的数据是%d\n&quot;, res);
					} catch (Exception e) {
						// TODO: handle exception
						System.out.println(e.getMessage());
					}
					break;
				case 'e': //退出
					scanner.close();
					loop = false;
					break;
				default:
					break;
			}
		}

		System.out.println(&quot;程序退出~~&quot;);
	}

}

// 使用数组模拟队列-编写一个ArrayQueue类
class ArrayQueue {
	private int maxSize; // 表示数组的最大容量
	private int front; // 队列头
	private int rear; // 队列尾
	private int[] arr; // 该数据用于存放数据, 模拟队列

	// 创建队列的构造器
	public ArrayQueue(int arrMaxSize) {
		maxSize = arrMaxSize;
		arr = new int[maxSize];
		front = -1; // 指向队列头部，分析出front是指向队列头的前一个位置.
		rear = -1; // 指向队列尾，指向队列尾的数据(即就是队列最后一个数据)
	}

	// 判断队列是否满
	public boolean isFull() {
		return rear == maxSize - 1;
	}

	// 判断队列是否为空
	public boolean isEmpty() {
		return rear == front;
	}

	// 添加数据到队列
	public void addQueue(int n) {
		// 判断队列是否满
		if (isFull()) {
			System.out.println(&quot;队列满，不能加入数据~&quot;);
			return;
		}
		rear++; // 让rear 后移
		arr[rear] = n;
	}

	// 获取队列的数据, 出队列
	public int getQueue() {
		// 判断队列是否空
		if (isEmpty()) {
			// 通过抛出异常
			throw new RuntimeException(&quot;队列空，不能取数据&quot;);
		}
		front++; // front后移
		return arr[front];

	}

	// 显示队列的所有数据
	public void showQueue() {
		// 遍历
		if (isEmpty()) {
			System.out.println(&quot;队列空的，没有数据~~&quot;);
			return;
		}
		for (int i = 0; i &lt; arr.length; i++) {
			System.out.printf(&quot;arr[%d]=%d\n&quot;, i, arr[i]);
		}
	}

	// 显示队列的头数据， 注意不是取出数据
	public int headQueue() {
		// 判断
		if (isEmpty()) {
			throw new RuntimeException(&quot;队列空的，没有数据~~&quot;);
		}
		return arr[front + 1];
	}
}

</code></pre>
<h2 id="5-优化_环形队列">5、优化_环形队列</h2>
<ul>
<li>
<p>问题分析并优化</p>
<ol>
<li>目前数组使用一次就不能用， 没有达到复用的效果</li>
<li>将这个数组使用算法，改进成一个列 <strong>环形的队列</strong> 取余：%</li>
</ol>
</li>
<li>
<p>分析说明：</p>
<ol>
<li>尾索引的下一个为头索引时表示队列满，即将队列容量空出一个作为约定,这个在做判断队列满的时候需要注意 (rear + 1) % maxSize == front 满]</li>
<li>rear == front [空]</li>
<li>分析示意图:</li>
</ol>
</li>
</ul>
<img src="file://C:/Users/zoick/OneDrive/Gridea/post-images/datastructure/array/5.png"  />
<p>代码实现</p>
<pre><code class="language-java">package datastructure.array;

import java.util.Scanner;

public class CircleArrayQueueDemo {

	public static void main(String[] args) {
		
		//测试一把
		System.out.println(&quot;测试数组模拟环形队列的案例~~~&quot;);
		
		// 创建一个环形队列
		CircleArray queue = new CircleArray(4); //说明设置4, 其队列的有效数据最大是3
		char key = ' '; // 接收用户输入
		Scanner scanner = new Scanner(System.in);//
		boolean loop = true;
		// 输出一个菜单
		while (loop) {
			System.out.println(&quot;s(show): 显示队列&quot;);
			System.out.println(&quot;e(exit): 退出程序&quot;);
			System.out.println(&quot;a(add): 添加数据到队列&quot;);
			System.out.println(&quot;g(get): 从队列取出数据&quot;);
			System.out.println(&quot;h(head): 查看队列头的数据&quot;);
			key = scanner.next().charAt(0);// 接收一个字符
			switch (key) {
			case 's':
				queue.showQueue();
				break;
			case 'a':
				System.out.println(&quot;输出一个数&quot;);
				int value = scanner.nextInt();
				queue.addQueue(value);
				break;
			case 'g': // 取出数据
				try {
					int res = queue.getQueue();
					System.out.printf(&quot;取出的数据是%d\n&quot;, res);
				} catch (Exception e) {
					// TODO: handle exception
					System.out.println(e.getMessage());
				}
				break;
			case 'h': // 查看队列头的数据
				try {
					int res = queue.headQueue();
					System.out.printf(&quot;队列头的数据是%d\n&quot;, res);
				} catch (Exception e) {
					// TODO: handle exception
					System.out.println(e.getMessage());
				}
				break;
			case 'e': // 退出
				scanner.close();
				loop = false;
				break;
			default:
				break;
			}
		}
		System.out.println(&quot;程序退出~~&quot;);
	}

}


class CircleArray {
	private int maxSize; // 表示数组的最大容量
	//front 变量的含义做一个调整： front 就指向队列的第一个元素, 也就是说 arr[front] 就是队列的第一个元素 
	//front 的初始值 = 0
	private int front; 
	//rear 变量的含义做一个调整：rear 指向队列的最后一个元素的后一个位置. 因为希望空出一个空间做为约定.
	//rear 的初始值 = 0
	private int rear; // 队列尾
	private int[] arr; // 该数据用于存放数据, 模拟队列

	// 创建队列的构造器
	public CircleArray(int arrMaxSize) {
		maxSize = arrMaxSize;
		arr = new int[maxSize];
	}
	
	// 判断队列是否满
	public boolean isFull() {
		return (rear  + 1) % maxSize == front;
	}
	
	// 判断队列是否为空
	public boolean isEmpty() {
		return rear == front;
	}
	
	// 添加数据到队列
	public void addQueue(int n) {
		// 判断队列是否满
		if (isFull()) {
			System.out.println(&quot;队列满，不能加入数据~&quot;);
			return;
		}
		//直接将数据加入
		arr[rear] = n;
		//将 rear 后移, 这里必须考虑取模
		rear = (rear + 1) % maxSize;
	}
	
	// 获取队列的数据, 出队列
	public int getQueue() {
		// 判断队列是否空
		if (isEmpty()) {
			// 通过抛出异常
			throw new RuntimeException(&quot;队列空，不能取数据&quot;);
		}
		// 这里需要分析出 front是指向队列的第一个元素
		// 1. 先把 front 对应的值保留到一个临时变量
		// 2. 将 front 后移, 考虑取模
		// 3. 将临时保存的变量返回
		int value = arr[front];
		front = (front + 1) % maxSize;
		return value;

	}
	
	// 显示队列的所有数据
	public void showQueue() {
		// 遍历
		if (isEmpty()) {
			System.out.println(&quot;队列空的，没有数据~~&quot;);
			return;
		}
		// 思路：从front开始遍历，遍历多少个元素
		// 动脑筋
		for (int i = front; i &lt; front + size() ; i++) {
			System.out.printf(&quot;arr[%d]=%d\n&quot;, i % maxSize, arr[i % maxSize]);
		}
	}

	// 求出当前队列有效数据的个数
	public int size() {
		// rear = 2
		// front = 1
		// maxSize = 3 
		return (rear + maxSize - front) % maxSize;   
	}
	
	// 显示队列的头数据， 注意不是取出数据
	public int headQueue() {
		// 判断
		if (isEmpty()) {
			throw new RuntimeException(&quot;队列空的，没有数据~~&quot;);
		}
		return arr[front];
	}
}
</code></pre>

              </div>
              <div class="toc-container">
                <ul class="markdownIt-TOC">
<li>
<ul>
<li><a href="#1-%E5%AE%9E%E9%99%85%E5%BA%94%E7%94%A8%E5%9C%BA%E6%99%AF">1、实际应用场景</a></li>
<li><a href="#2-%E9%98%9F%E5%88%97%E4%BB%8B%E7%BB%8D">2、队列介绍</a></li>
<li><a href="#3-%E6%95%B0%E7%BB%84%E6%A8%A1%E6%8B%9F%E9%98%9F%E5%88%97%E6%80%9D%E8%B7%AF">3、数组模拟队列思路</a></li>
<li><a href="#4-%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0">4、代码实现</a></li>
<li><a href="#5-%E4%BC%98%E5%8C%96_%E7%8E%AF%E5%BD%A2%E9%98%9F%E5%88%97">5、优化_环形队列</a></li>
</ul>
</li>
</ul>

              </div>
            </div>
          </article>
        </div>

        
          <div class="next-post">
            <div class="next">下一篇</div>
            <a href="https://ArtZoick.github.io//post/array">
              <h3 class="post-title">
                1、数据结构之稀疏数组
              </h3>
            </a>
          </div>
        

        
          
            <link rel="stylesheet" href="https://unpkg.com/gitalk/dist/gitalk.css">
<script src="https://unpkg.com/gitalk/dist/gitalk.min.js"></script>

<div id="gitalk-container"></div>

<script>

  var gitalk = new Gitalk({
    clientID: 'a2471d09bddb5be481ee',
    clientSecret: '05d427fb27f873cfabace27b9f042f2c7f23000f',
    repo: 'ArtZoick.github.io',
    owner: 'ArtZoick',
    admin: ['ArtZoick'],
    id: (location.pathname).substring(0, 49),      // Ensure uniqueness and length less than 50
    distractionFreeMode: false  // Facebook-like distraction free mode
  })

  gitalk.render('gitalk-container')

</script>

          

          
        

        <div class="site-footer">
  <a href="https://zhidao.baidu.com/question/1867120235416383707.html" target="_blank" onclick="alert('盲生，你发现了华点！');">学习强国</a>

<!--Tido对话插件-->
<script src="//code.tidio.co/5fh6jaqvluqj8jjuf5zlqrf5tlzpktnx.js"></script>
<style>
.text-popup {
    animation: textPopup 1s;
    color: red;
    user-select: none;
    white-space: nowrap;
    position: absolute;
    z-index: 99;
}
@keyframes textPopup {
    0%, 100% {
        opacity: 0;
    }
    5% {
        opacity: 1;
    }
    100% {
        transform: translateY(-50px);    
    }
}
</style>
<script type="text/javascript" src="https://cdn.bootcss.com/canvas-nest.js/1.0.1/canvas-nest.min.js">
!function(){function n(n,e,t){return n.getAttribute(e)||t}function e(n){return document.getElementsByTagName(n)}
function t(){var t=e("script"),o=t.length,i=t[o-1];return{l:o,z:n(i,"zIndex",-1),o:n(i,"opacity",.5),c:n(i,"color","0,0,0")
,n:n(i,"count",99)}}function o(){a=m.width=window.innerWidth||document.documentElement.clientWidth||document.body.clientWidt
h,c=m.height=window.innerHeight||document.documentElement.clientHeight||document.body.clientHeight}function i(){r.clearRect
(0,0,a,c);var n,e,t,o,m,l;s.forEach(function(i,x){for(i.x+=i.xa,i.y+=i.ya,i.xa*=i.x>a||i.x<0?-1:1,i.ya*=i.y>c||i.y<0?-1:1,r.
fillRect(i.x-.5,i.y-.5,1,1),e=x+1;e<u.length;e++)n=u[e],null!==n.x&&null!==n.y&&(o=i.x-n.x,m=i.y-n.y,l=o*o+m*m,l<n.max&&(n===
y&&l>=n.max/2&&(i.x-=.03*o,i.y-=.03*m),t=(n.max-l)/n.max,r.beginPath(),r.lineWidth=t/2,r.strokeStyle="rgba("+d.c+","+(t+.2)+")
",r.moveTo(i.x,i.y),r.lineTo(n.x,n.y),r.stroke()))}),x(i)}var a,c,u,m=document.createElement("canvas"),d=t(),l="c_n"+d.l,r=m.
getContext("2d"),x=window.requestAnimationFrame||window.webkitRequestAnimationFrame||window.mozRequestAnimationFrame||window.
oRequestAnimationFrame||window.msRequestAnimationFrame||function(n){window.setTimeout(n,1e3/45)},w=Math.random,y={x:null,y:nul
l,max:2e4};m.id=l,m.style.cssText="position:fixed;top:0;left:0;z-index:"+d.z+";opacity:"+d.o,e("body")[0].appendChild(m),o(),
window.οnresize=o,window.οnmοusemοve=function(n){n=n||window.event,y.x=n.clientX,y.y=n.clientY},window.οnmοuseοut=function(){y
.x=null,y.y=null};for(var s=[],f=0;d.n>f;f++){var h=w()*a,g=w()*c,v=2*w()-1,p=2*w()-1;s.push({x:h,y:g,xa:v,ya:p,max:6e3})}u=
s.concat([y]),setTimeout(function(){i()},100)}();
</script>

<!--鼠标点击-->
<!--富强-->
<script type="text/javascript"> 
/* 鼠标特效 */ 
var a_idx = 0; 
jQuery(document).ready(function($) { 
    $("body").click(function(e) { 
        var a = new Array("富强", "民主", "文明", "和谐", "自由", "平等", "公正" ,"法治", "爱国", "敬业", "诚信", "友善"); 
        var $i = $("<span/>").text(a[a_idx]); 
        a_idx = (a_idx + 1) % a.length; 
        var x = e.pageX, 
        y = e.pageY; 
        $i.css({ 
            "z-index": 999, 
            "top": y - 20, 
            "left": x, 
            "position": "absolute", 
            "font-weight": "bold", 
            "color": "#ff6651" 
        }); 
        $("body").append($i); 
        $i.animate({ 
            "top": y - 180, 
            "opacity": 0 
        }, 
        1500, 
        function() { 
            $i.remove(); 
        }); 
    }); 
}); 
</script>
<!--edn--富强--> | 
  <a class="rss" href="https://ArtZoick.github.io//atom.xml" target="_blank">RSS</a>
</div>

<script>
  hljs.initHighlightingOnLoad()

  let mainNavLinks = document.querySelectorAll(".markdownIt-TOC a");

  // This should probably be throttled.
  // Especially because it triggers during smooth scrolling.
  // https://lodash.com/docs/4.17.10#throttle
  // You could do like...
  // window.addEventListener("scroll", () => {
  //    _.throttle(doThatStuff, 100);
  // });
  // Only not doing it here to keep this Pen dependency-free.

  window.addEventListener("scroll", event => {
    let fromTop = window.scrollY;

    mainNavLinks.forEach((link, index) => {
      let section = document.getElementById(decodeURI(link.hash).substring(1));
      let nextSection = null
      if (mainNavLinks[index + 1]) {
        nextSection = document.getElementById(decodeURI(mainNavLinks[index + 1].hash).substring(1));
      }
      console.log('section.offsetHeight', section.offsetHeight);
      if (section.offsetTop <= fromTop) {
        if (nextSection) {
          if (nextSection.offsetTop > fromTop) {
            link.classList.add("current");
          } else {
            link.classList.remove("current");    
          }
        } else {
          link.classList.add("current");
        }
      } else {
        link.classList.remove("current");
      }
    });
  });

</script>

      </div>
    </div>
  </body>
</html>
